import java.util.*;

/**
 * 题目：考古学家
 * 
 * 题目描述：
 * 考古学家发现了一块石碑，石碑被整齐地切成了n块。请帮助考古学家恢复石碑的原始内容，
 * 找出所有可能的石碑文本组合。
 * 
 * 输入描述：
 * 第一行输入一个整数n，表示石碑碎片的个数。
 * 第二行输入n个字符串s，表示每个石碑碎片的文本内容。
 * 
 * 输出描述：
 * 输出所有可能的石碑文本组合，按字典序升序排列，每个组合占一行，行末不要有多余空格。
 * 
 * 备注：
 * 如果石碑碎片有相同的内容，那么它们顺序的变化不会影响恢复的石碑文本。
 * 也就是说，相同碎片的排列不会影响组合。
 * 
 * 示例1：
 * 输入：
 * 3
 * a
 * b
 * c
 * 输出：
 * abc
 * acb
 * bac
 * bca
 * cab
 * cba
 * 
 * 解题思路：
 * 这是一个多重集合的排列问题，需要生成所有不重复的排列。
 * 
 * 算法分析：
 * - 时间复杂度：O(n! * m) 其中m是字符串长度
 * - 空间复杂度：O(n! * m)
 * - 算法类型：回溯算法，排列生成
 */
public class Archaeologist {
    
    /**
     * 方法1：回溯算法法（推荐使用）
     * 使用回溯算法生成所有不重复的排列
     * 
     * 算法思路：
     * 1. 统计每个字符串的出现次数
     * 2. 使用回溯算法生成所有排列
     * 3. 避免重复排列的生成
     * 
     * 时间复杂度：O(n! * m)
     * 空间复杂度：O(n! * m)
     */
    public static List<String> generateCombinations1(String[] fragments) {
        List<String> result = new ArrayList<>();
        Map<String, Integer> count = new HashMap<>();
        
        // 统计每个字符串的出现次数
        for (String fragment : fragments) {
            count.put(fragment, count.getOrDefault(fragment, 0) + 1);
        }
        
        // 使用回溯算法生成排列
        backtrack(count, new StringBuilder(), result, fragments.length);
        
        // 按字典序排序
        Collections.sort(result);
        return result;
    }
    
    private static void backtrack(Map<String, Integer> count, StringBuilder current, 
                                 List<String> result, int totalLength) {
        if (current.length() == totalLength) {
            result.add(current.toString());
            return;
        }
        
        for (String fragment : count.keySet()) {
            if (count.get(fragment) > 0) {
                // 选择当前片段
                count.put(fragment, count.get(fragment) - 1);
                current.append(fragment);
                
                // 递归
                backtrack(count, current, result, totalLength);
                
                // 回溯
                current.setLength(current.length() - fragment.length());
                count.put(fragment, count.get(fragment) + 1);
            }
        }
    }
    
    /**
     * 方法2：递归生成法
     * 使用递归方式生成所有排列
     * 
     * 算法思路：
     * 1. 将字符串数组转换为列表
     * 2. 使用递归生成所有排列
     * 3. 使用Set去重
     * 
     * 时间复杂度：O(n! * m)
     * 空间复杂度：O(n! * m)
     */
    public static List<String> generateCombinations2(String[] fragments) {
        Set<String> result = new HashSet<>();
        List<String> fragmentList = new ArrayList<>(Arrays.asList(fragments));
        
        generatePermutations(fragmentList, new ArrayList<>(), result);
        
        List<String> sortedResult = new ArrayList<>(result);
        Collections.sort(sortedResult);
        return sortedResult;
    }
    
    private static void generatePermutations(List<String> remaining, List<String> current, Set<String> result) {
        if (remaining.isEmpty()) {
            result.add(String.join("", current));
            return;
        }
        
        for (int i = 0; i < remaining.size(); i++) {
            String fragment = remaining.get(i);
            current.add(fragment);
            remaining.remove(i);
            
            generatePermutations(remaining, current, result);
            
            current.remove(current.size() - 1);
            remaining.add(i, fragment);
        }
    }
    
    /**
     * 方法3：字典序生成法
     * 使用字典序生成所有排列
     * 
     * 算法思路：
     * 1. 先对字符串数组排序
     * 2. 使用字典序算法生成下一个排列
     * 3. 直到没有下一个排列为止
     * 
     * 时间复杂度：O(n! * m)
     * 空间复杂度：O(n! * m)
     */
    public static List<String> generateCombinations3(String[] fragments) {
        List<String> result = new ArrayList<>();
        Arrays.sort(fragments);
        
        do {
            result.add(String.join("", fragments));
        } while (nextPermutation(fragments));
        
        return result;
    }
    
    private static boolean nextPermutation(String[] arr) {
        int i = arr.length - 2;
        while (i >= 0 && arr[i].compareTo(arr[i + 1]) >= 0) {
            i--;
        }
        
        if (i < 0) return false;
        
        int j = arr.length - 1;
        while (arr[j].compareTo(arr[i]) <= 0) {
            j--;
        }
        
        swap(arr, i, j);
        reverse(arr, i + 1, arr.length - 1);
        return true;
    }
    
    private static void swap(String[] arr, int i, int j) {
        String temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    
    private static void reverse(String[] arr, int start, int end) {
        while (start < end) {
            swap(arr, start, end);
            start++;
            end--;
        }
    }
    
    /**
     * 方法4：堆算法法
     * 使用堆算法生成所有排列
     * 
     * 算法思路：
     * 1. 使用堆算法生成所有排列
     * 2. 堆算法是一种高效的排列生成算法
     * 3. 使用Set去重
     * 
     * 时间复杂度：O(n! * m)
     * 空间复杂度：O(n! * m)
     */
    public static List<String> generateCombinations4(String[] fragments) {
        Set<String> result = new HashSet<>();
        heapAlgorithm(fragments, fragments.length, result);
        
        List<String> sortedResult = new ArrayList<>(result);
        Collections.sort(sortedResult);
        return sortedResult;
    }
    
    private static void heapAlgorithm(String[] arr, int n, Set<String> result) {
        if (n == 1) {
            result.add(String.join("", arr));
            return;
        }
        
        for (int i = 0; i < n; i++) {
            heapAlgorithm(arr, n - 1, result);
            
            if (n % 2 == 1) {
                swap(arr, 0, n - 1);
            } else {
                swap(arr, i, n - 1);
            }
        }
    }
    
    /**
     * 方法5：优化回溯法
     * 使用优化的回溯算法，减少重复计算
     * 
     * 算法思路：
     * 1. 使用频率数组代替Map
     * 2. 优化字符串拼接操作
     * 3. 使用更高效的数据结构
     * 
     * 时间复杂度：O(n! * m)
     * 空间复杂度：O(n! * m)
     */
    public static List<String> generateCombinations5(String[] fragments) {
        List<String> result = new ArrayList<>();
        Map<String, Integer> count = new HashMap<>();
        
        // 统计频率
        for (String fragment : fragments) {
            count.put(fragment, count.getOrDefault(fragment, 0) + 1);
        }
        
        // 获取唯一的字符串
        String[] uniqueFragments = count.keySet().toArray(new String[0]);
        int[] frequencies = new int[uniqueFragments.length];
        for (int i = 0; i < uniqueFragments.length; i++) {
            frequencies[i] = count.get(uniqueFragments[i]);
        }
        
        // 优化回溯
        optimizedBacktrack(uniqueFragments, frequencies, new StringBuilder(), result, fragments.length);
        
        Collections.sort(result);
        return result;
    }
    
    private static void optimizedBacktrack(String[] uniqueFragments, int[] frequencies, 
                                         StringBuilder current, List<String> result, int totalLength) {
        if (current.length() == totalLength) {
            result.add(current.toString());
            return;
        }
        
        for (int i = 0; i < uniqueFragments.length; i++) {
            if (frequencies[i] > 0) {
                frequencies[i]--;
                current.append(uniqueFragments[i]);
                
                optimizedBacktrack(uniqueFragments, frequencies, current, result, totalLength);
                
                current.setLength(current.length() - uniqueFragments[i].length());
                frequencies[i]++;
            }
        }
    }
    
    /**
     * 主方法 - 程序入口
     */
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取输入
        System.out.println("请输入石碑碎片个数n：");
        int n = scanner.nextInt();
        scanner.nextLine(); // 消费换行符
        
        System.out.println("请输入" + n + "个石碑碎片（每行一个）：");
        String[] fragments = new String[n];
        for (int i = 0; i < n; i++) {
            fragments[i] = scanner.nextLine();
        }
        
        // 测试所有方法
        System.out.println("\n=== 所有算法结果对比 ===");
        
        List<String> result1 = generateCombinations1(fragments);
        List<String> result2 = generateCombinations2(fragments);
        List<String> result3 = generateCombinations3(fragments);
        List<String> result4 = generateCombinations4(fragments);
        List<String> result5 = generateCombinations5(fragments);
        
        System.out.println("方法1（回溯算法法）结果数量: " + result1.size());
        System.out.println("方法2（递归生成法）结果数量: " + result2.size());
        System.out.println("方法3（字典序生成法）结果数量: " + result3.size());
        System.out.println("方法4（堆算法法）结果数量: " + result4.size());
        System.out.println("方法5（优化回溯法）结果数量: " + result5.size());
        
        // 输出结果（以方法1为例）
        System.out.println("\n=== 所有可能的组合 ===");
        for (String combination : result1) {
            System.out.println(combination);
        }
        
        // 推荐使用的方法
        System.out.println("\n推荐使用方法1（回溯算法法），逻辑清晰且效率高");
        
        scanner.close();
    }
}
